package a15_MapAndSet;

/**
 * @Author quan
 * @Description 开散列形式的HashMap实现
 * @Date 2023/4/29 17:26
 */
public class HashMapCodes {
    /**
     * 组成：数组和链表构成。普通的数组是每个位置保存一个值，HashMap则是每个位置保存一个链表
     * 注意：这里的链表中的每个节点存储的是一个键值对。
     */
    //定义可以存储链表的数组
    private Node[] data;
    //定义当前哈希表的有效元素个数
    private int size;
    //定义内部的Node节点
    private static class Node{
        int key;
        int value;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    //定义取模数：简单起见，让数组的取模数和数组元素个数一致
    private int M;
    //定义负载因子
    private static final double LOAD_FACTOR = 0.75;
    //构造方法
    public HashMapCodes() {
        this(16);
    }
    public HashMapCodes(int capacity) {
        this.data = new Node[capacity];
        this.M = capacity;
    }

    /**
     * put:新增或者修改元素：在当前哈希表中添加一对新元素，返回添加前的值
     * @param key
     * @param value
     * @return 如果是新元素，则返回-1
     */
    public int put(int key,int value){
        //1、将该新增的值进行哈希函数计算在当前数组中的索引位置
        int index = hashFun(key);
        //2、在当前的索引位置判断该位置下的索引链表中是否存在该值:若存在，则只需要更细value即可
        //遍历对应索引下的链表
        for (Node x = data[index]; x != null; x=x.next) {
            //说明该元素已存在
            if(x.key == key){
                //获取旧键值对中的值
                int odValue = x.value;
                //更新对应key下的value值即可
                x.value = value;
                return odValue;
            }
        }
        //3、若不存在该key值，则说明该元素是第一次出现，将该元素头插到当前索引下的子链表中
        //产生该节点
        Node node = new Node(key,value);
        //当前子链表的头部与新节点建立联系：data[index]是子链表的头部
        node.next = data[index];
        //此时链表的头部就是新节点
        data[index] = node;
        //更新元素个数
        size++;
        //判断当前哈希表是否需要扩容
        if(size >= data.length * LOAD_FACTOR){
            resize();
        }
        return -1;
    }

    /**
     * 扩容方法：一共三步
     */
    private void resize() {
        //1、创建一个新数组：大小为原数组的2倍
        this.M = data.length << 1;
        Node[] newData = new Node[data.length << 1];
        //2、计算原数组中的每一个值经过新的哈希函数后得到的在新数组中的新索引值。
        // 找数组中每个元素使用双层for循环：外层循环遍历原数组的每一个位置，内层元素则是数组每一个位置上的子链表的遍历
        //数组中每一个位置
        for (int i = 0; i < data.length; i++) {
            //子链表的遍历
            for (Node x = data[i]; x!= null;) {
                //暂存该节点的下一个节点
                Node next = x.next;
                //将该节点头插到新数组的新索引处
                //计算新索引
                int newIndex = hashFun(x.key);
                //头插到新数组
                x.next = newData[newIndex];
                newData[newIndex] = x;
                //指向下一个节点
                x = next;
            }
        }
        //3、更新数组为新数组
        data = newData;
    }

    /**
     * 通过key值删除指定值
     * 如果通过value值删除，由于value值可能会重复，因此会误删。
     * @param key
     * @return
     */
    public boolean removeByKey(int key){
        //1、计算key值经过哈希函数后的索引
        int index = hashFun(key);
        //边界条件
        if(data[index] == null){
            return false;
        }
        //2、此时就是该索引位置上子链表的删除
        //(1)如果该链表头结点就是待删除元素
        if(data[index].key == key){
            //更新子链表的头结点
            data[index] = data[index].next;
            size--;
            return true;
        }
        //(2)不是头结点的链表删除:通过前驱节点删除
        //当前子链表的头部作为前驱
        Node prev = data[index];
        //如果不到最后一个节点，就一直遍历
        while (prev.next != null){
            if(prev.next.key == key){
                //找到待删除的节点，更改节点的指向
                prev.next = prev.next.next;
                //更新节点个数
                size--;
                return true;
            }
        }
        //没有找到被删除的元素
        return false;
    }

    /**
     * 判断当前hashMap中是否包含给定的key值
     * @param key
     * @return
     */
    public boolean containsKey(int key){
        //1、计算给定值的索引位置
        int index = hashFun(key);
        //2、遍历该位置索引下的子链表，判断该key值是否存在:data[index]表示子链表的头部
        for (Node x = data[index]; x != null ; x=x.next) {
            if(x.key == key){
                return true;
            }
        }
        return false;
    }

    /**
     * 判断当前数组中是否含有指定的value值 -> 全表扫描
     * 因为hash函数是根据key值计算索引的，所以上面判断是否包含key，则只需要在对应的索引位置下的子链表查找
     * 但是value则要在整个数组的所有链表都遍历，也叫作全表扫描。
     * @param value
     * @return
     */
    public boolean containsValue(int value){
        //外层：数组中的每个元素都是一个链表
        for (int i = 0; i < data.length; i++) {
            //内层：遍历每个子链表的节点
            for (Node x = data[i]; x != null ; x = x.next) {
                if(x.value == value){
                    return true;
                }
            }
        }
        return false;
    }
    /**
     * 返回给定值经过哈希函数计算后的在数组中的索引值
     * @param i
     * @return
     */
    private int hashFun(int i) {
        return i % M;
    }
}
